package com.lfg.leetcode.leetcode100;

import com.lfg.leetcode.leetcode0.TreeNode;

import java.util.Stack;

public class BSTIterator {
    Stack<TreeNode> stack = new Stack<TreeNode>();

    public BSTIterator(TreeNode root) {
        TreeNode children = root;
        while (children != null) {
            stack.push(children);
            children = children.left;
        }
    }

    public static void main(String[] args) {


        BSTIterator iterator = new BSTIterator(TreeNode.stringToTreeNode("[7,3,15,null,null,9,20]"));
        System.out.println(iterator.next());    // 返回 3
        System.out.println(iterator.next());    // 返回 7
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());    // 返回 9
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());    // 返回 15
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());    // 返回 20
        System.out.println(iterator.hasNext()); // 返回 false
    }

    public int next() {
        TreeNode node = stack.pop();
        TreeNode children = node.right;
        while (children != null) {
            stack.push(children);
            children = children.left;
        }
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}
